#include <stdio.h>

#define NUM 17


/*
 * about quck sort 
 */
int partition(int data[], int low, int high)
{
	int i = low, j = high;
	int pivot = data[i];
	while (i < j) {
		while (i < j && data[j] >= pivot)
			j--;
		if(i < j) {
			data[i] = data[j];
			i++;
		}

		while(i < j && data[i] <=  pivot)
			i++;
		if (i < j) {
			data[j] = data[i];
			j--;
		}
	}
	data[i] = pivot;

	{
		int k = 0;
		for (k = 0; k < NUM; k++)
			printf("%d  ", data[k]);
		printf("\n");
	}

	return i;
}

void quick_sort(int data[], int low, int high)
{
	int part_pos;
	part_pos = partition(data, low, high);
	if (low < high - 1) 
		quick_sort(data, low, part_pos - 1);
	if (part_pos + 1 < high) 
		quick_sort(data, part_pos + 1, high);
}


/*
 * about bubble sort
 */

void bubble_sort(int data[], int num)
{
	int i, j, tmp;
	for(i = 0; i < num; i++) {
		for (j = 1; j < num -i; j++) {
			if (data[j -1] <= data[j])
				continue;
			tmp = data[j];
			data[j] = data[j-1];
			data[j-1] = tmp;
		}
	}
}

int main () 
{
	int data[NUM] = {6, 9, 7, 8, 0, 19, 12, 16, 13, 11, 18, 14, 1, 3, 2, 5, 4};
	int i;

//	quick_sort(data, 0, NUM - 1);
	bubble_sort(data, NUM);

	for (i = 0; i < NUM; i++)
		printf("%d  ", data[i]);
	printf("\n");

	return 0;
}

